Early computer networks consisted of a small number of devices attached together using a single cable. Computer networks have since evolved, however, beyond a simple collection of attached devices. Current computer networks may connect thousands of devices spread across large local areas, and these local area networks may in turn be connected together to form still larger networks such as, for example, the Internet.
Today's computer networks often interconnect widely-disparate devices distributed throughout multiple local networks into a single virtual network. Virtual networking technology allows devices located on a single physical network to operate as part of multiple virtual networks. Such virtual networks provide flexibility not available in early computer networks and allow network administrators to create layers of abstraction to simplify complex network topologies. For example, using a virtual network, an enterprise may have a virtual blade server chassis with routers spread across multiple physical locations that allow a data center, which is split across multiple sites, to act as if the data center is at a single site.
The predominate standard used to construct and access today's computer networks is Ethernet. Ethernet is a family of frame-based computer networking technologies for local area networks. Ethernet is promulgated by the Institute of Electrical and Electronics Engineers (IEEE) in various standards specifications as part of the IEEE 802 family of standards. Ethernet defines a number of wiring and signaling standards for the Physical Layer of the Open Systems Interconnection (OSI) Networking Model, the means for network access at the Media Access Control (MAC) and Data Link Layer, and a common addressing format. At the physical layer, Ethernet networks are ubiquitous, carrying all kinds of traffic over multiple types of physical connections (wired or wireless), including 10 Mbps, 100 Mbps, 1 Gbps, 10 Gbps, 100 Gbps connections. The Ethernet service layer, generally referred to as Layer-2 because it is the MAC and Data Link Layer in the OSI networking model, provides the services generally required by a network. These network services typically include filtering, replication, forwarding broadcast, unicast, and multicast (BUM) traffic, and following a serviced topology, which may include virtual local area networks (VLANs), ATM segments of VLANs based on the ATM Lane Standard (ELANs), Ethernet Private Lines (ELINEs), and rooted multipoint Ethernet virtual connections (ETREEs).
VLAN services are specified in the IEEE 802.1Q standard and allow enterprise customers to configure various computing devices to communicate as if those devices were attached to the same broadcast domain, regardless of their physical locations. VLANs provide segmentation services traditionally provided by routers in local area network (LAN) configurations and address issues such as scalability, security, and network management. Bridges in VLAN topologies enforce the integrity of VLAN broadcast domains because such bridges are not permitted to bridge network traffic between VLANs. In this way, VLANs may provide broadcast filtering, security, address summarization, and traffic flow management. Network administrators may use VLANs to create multiple Layer 3 networks on the same Layer-2 bridge. For example if a Dynamic Host Configuration Protocol (DHCP) server, which broadcasts its presence, were plugged into a bridge, the DHCP server would serve any host device connected to the bridge. By using VLANs, however, a network administrator may easily split up the devices on the network so that some hosts will not use that DHCP server and will default to link-local addresses.
Because enterprise customers often have multiple networks distributed across multiple physical sites, customer's typically connected these physically separate networks together through the network of a network provider. For example, a company may connect its network at site A to its network at site B through a network provided by a telecommunications company. Despite the customer networks being connected through a provider network, devices on the different customer networks may still use VLAN services to communicate through the provider's network as though the devices were all located on the same LAN.
For the same reasons that enterprise customers take advantage of the VLAN services described in the IEEE 802.1Q specification, network providers also take advantage of VLAN services to provide flexibility, security, traffic flow management, and reduce their network administration burden. The drawback, however, is that under the IEEE 802.1Q specification, there are only 4096 identifiers available to specify different VLANs. Thus, a network provider and all the customers that provider serves must share the 4096 VLAN identifiers.
Because industry participants deemed such a limited number of VLAN identifiers inadequate to meet the needs of both customers and providers, the IEEE 802.1Q standard was amended by the IEEE 802.ad standard, often referred to as “Q-in-Q” or “stacked VLANs.” The IEEE 802.ad standard sets forth an architecture and bridge protocol to provide separate instances of MAC network services to multiple independent users of a provider network in a manner that does not require cooperation among the customers, and requires a minimum of cooperation between the customers and the provider of the MAC network service. Q-in-Q provides customers with the ability to configure their own VLANs inside the VLAN provided to the customer by a service provider. In such a manner, the service provider may configure one service VLAN for the customer, and the customer can utilize that service VLAN to establish multiple customer VLANs.
To provide an overview of Ethernet header stacking of encapsulation, FIG. 1 sets forth a line drawing that illustrates exemplary Ethernet frame structures compliant with the IEEE 802.1 family of standards. FIG. 1 illustrates a traditional Ethernet frame 100 implemented in a customer's network according to the IEEE 802.1D standard. The customer frame 100 consists of a payload 101, a header type (EthType) 102 indicating that frame 100 is an 802.1D frame, a customer network source MAC address (C-SA) 103, and a customer network destination MAC address (C-DA) 104. The customer network source MAC address 103 specifies the source node in the customer network that originates the frame 100, while the customer network destination MAC address 104 specifies the destination node in the customer network to which the frame is bound for delivery.
As mentioned above, a customer may organize the nodes into various VLANs to provide traffic flow management, security, ease network administration, and the like. VLANs established by a customer for use within the customer's networks are generally referred to a ‘customer VLANs.’ In a network using customer VLANs, frame 100 is encapsulated as frame 110 to include a customer VLAN identifier (C-VID) 115 and a new header type (EthType) 116, indicating that the frame 110 is an 802.1Q frame. As used in this application, encapsulation may allow additional fields to be placed in any position relative to the encapsulated object, including interior to the original object, and does not require the additional fields be placed surrounding or at either end of the encapsulated object.
In a provider bridge (PB) network that bridges two customer networks, the frame 110 is further encapsulated as shown by frame 120, adding new fields for: a service VLAN identifier (S-VID) 127, and a new header type (EthType) 128 indicating the frame 120 is IEEE 802.1ad compliant.
For further explanation of header stacking or encapsulation in a IEEE 802.1ad provider bridge network, FIGS. 2 and 3 set forth network diagrams that illustrate an exemplary provider bridge network 200 interconnecting exemplary networks for customers A and B (201 and 202, respectively). In FIGS. 2 and 3, customer A 201 maintains three networks 203, 205, 207, while customer B 202 maintains two networks 204, 206. The provider bridge network 200 consists of six bridges, four provider edge bridges (PEB) 1-4 and two provider core bridges (PCB) 1-2. An edge bridge is a bridge through which frames ingress and egress the network 200—that is, an edge bridge is positioned at the ‘edge’ of the network topology. A core bridge is a bridge used to interconnect one or more edge bridges.
FIG. 2 illustrates a frame 220 at several stages as the frame 220 traverses the networks of FIG. 2 from customer equipment (CE)-11 210 in network 203 of customer A 201 to CE-31 212 in network 205 of customer A 201. In FIG. 2, the communications between CE-11 210 and CE-31 212 are implemented using a customer VLAN, and so the frame 220a from CE-11 210 is encapsulated with a customer VLAN header 230 that includes a customer VLAN identifier (C-VID) and a header type (EthType) specifying that the frame 220a is an IEEE 802.1Q compliant frame. The frame 220 includes a source MAC address (CE-11-SA) for CE-11 210, which indicates that CE-11 210 originated the frame 220a, and a destination MAC address (CE-31-DA) for CE-31 212, which indicates that the frame 220 is destined for CE-31 212.
When provider edge bridge (PEB)-1 240 receives the frame 220a, PEB-1 240 encapsulates the frame 220a into an 802.1ad frame 220b by adding a service VLAN header 231 to the frame 220. The service VLAN header 231 includes a service VLAN identifier (S-VID-A) assigned by the provider to customer A 201 and a header type (EthType) specifying that the frame is IEEE 802.1ad compliant. Using the service VLAN identifier and customer MAC addresses to identify devices in the networks 203, 205, 207 of customer A 201, the provider bridges learn information about the MAC addresses of the computing devices in customer A's networks. From the learned MAC information, the provider bridges route the frame 220 through the provider network 200 from the PEB-1 240 through which the frame 220 ingresses the network 200 to the PEB-3 242 through which the frame 220 egresses the network 200. PEB-3 242 then de-encapsulates the frame 220b by removing to service VLAN header 231, leaving IEEE 802.1Q compliant frame 220a for delivery to CE-31 212.
Similarly, in FIG. 3, computing device CE-15 310 in network 204 of customer B 202 sends an IEEE 802.1Q compliant frame 320a to device CE-25 312 customer B's network 206. At PEB-1 240, frame 320a is encapsulated with a service VLAN header 331. The service VLAN header 331 includes a service VLAN identifier (S-VID-B) assigned by the service provider to customer B 202 and a header type (EthType) specifying that the frame is IEEE 802.1ad compliant. The ingress bridge 240 of the provider network 200 forwards the frame 320b to the egress bridge 342 of the provider network 200, which in turn de-encapsulates the frame 320b by removing the service VLAN header 331, leaving IEEE 802.1Q compliant frame 320a for delivery to CE-35 312. As the provider bridges receive various frames on their ports, the bridges learn the MAC addresses of the devices in customer B network by monitoring the MAC addresses associated with each service VLAN identifier assigned to customer B 202 by the network provider.
From the description above, readers will note that in a provider bridge network, the service provider uses one or more service VLANs to transport frames for a customer's VLANs between multiple customer networks. To determine the forwarding path for each service VLAN through the provider's bridge network, the provider bridges often use the Generic VLAN registration protocol (GVRP) or the Multiple VLAN Registration Protocol (MVRP). For multicast traffic containment, provider bridges may use the Generic Attribute Registration Protocol Multicast Registration Protocol (GMRP) or the Multiple Multicast Registration Protocol (MMRP). For purposes of forwarding traffic, provider edge bridges learn all customer equipment MAC addresses and forward customer frames based on the service VLAN identifier and customer VLAN identifier pairs, while provider core bridges learn all customer equipment MAC addresses, but forward customer frames based only on the service VLAN identifiers. Within a particular provider bridge network, a given customer equipment MAC address is at the same site for all service VLANs.
As noted, the advantage of the networks described with reference to FIGS. 2 and 3 is that these networks overcome the 4096 VLAN namespace limitation inherent in IEEE 802.1Q networks through use of a second VLAN namespace—that is, the service VLAN namespace. For each service VLAN identifier used by a particular customer, that customer may create 4096 customer VLANs, which effectively allows for a maximum of 16,777,216 customer VLANs when considering that there are 4096 service VLANs available.
The drawback to current networks such as those in FIGS. 2 and 3, however, is that frames are forwarded through the network using spanning trees established using a spanning tree protocol. The spanning tree protocol is an OSI Layer-2 protocol that ensures a loop-free topology for any bridged LAN. This protocol allows a network design to include spare (redundant) links to provide automatic backup paths if an active link fails, without the danger of bridge loops, or the need for manual enabling or disabling of these backup links. Bridge loops must be avoided because such loops result in traffic that floods the network. A spanning tree protocol, such as the one defined in the IEEE 802.1D standard, creates a spanning tree within a mesh network of connected Layer-2 bridges, and disables those links that are not part of the tree, leaving a single active path between any two network nodes.
There are certain disadvantages to the spanning tree protocol used in the networks described above with reference to FIGS. 2 and 3. Because the spanning tree protocol disables links that are not part of the forwarding tree, bottlenecks are often created by concentrating traffic onto selected links. Also, due to the nature of the spanning tree protocol, temporary loops may develop if spanning tree messages are lost or as the network topology changes because nodes are brought on-line or taken off-line or moved in the network. During periods when temporary loops exists, frames may flood the network because the standard Ethernet header does not contain a time-to-live field or hop count that specifies when a frame has become stale and should be discarded. Further, the paths developed between nodes of the network are not necessarily the pair-wise shortest path, but rather are the paths that remain after the spanning tree protocol eliminates redundant paths.
To overcome the disadvantages of the spanning tree protocol in IEEE 802.1Q networks, designers have developed network architectures that allow shortest path bridging in these IEEE 802.1Q networks. As mentioned above, however, IEEE 802.1Q networks are limited to the use of 4096 VLAN identifiers. The network solutions currently implemented to provide shortest path bridging in these networks further reduce the number of available VLAN identifiers to 4096 divided by the number of edge bridges in the shortest path bridging network. For example, when an SPB network includes thirty-two such bridges, then only 128 VLAN identifiers are typically available for creating VLANs because the bridges utilize the other 3968 VLAN identifiers to implement shortest path bridging. Reducing the number of VLAN identifiers available in this network by such a large amount often deprives or greatly reduces the benefits that VLANs provide to customers.